/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * assignment1
 * Copyright (C)  2010 <>
 *
 * assignment1 is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * assignment1 is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "s-f-game.h"
using namespace std;
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <cstring>
#include <boost/regex.hpp>
#include <boost/algorithm/string/regex.hpp>
#include <boost/lexical_cast.hpp>
#include <cmath>

#include <boost/regex.hpp>
#include <boost/foreach.hpp>

#include <iostream>
#include <string>
#include "circularlist.h"
#include "utilityNode.h"
#include "simplelist.h"
#include <boost/xpressive/xpressive.hpp>

using namespace boost;

char SFGame::DELIMITER ='|';
int SFGame::tabuCounter = 0;
double SFGame::PSNE = 1;
double SFGame::SDSE = 2;
double SFGame::WDSE = 3;
double SFGame::IDSE = 4;

SFGame::SFGame(std::string rootFolder) {
	//outputFile.open("/home/rohithdv/rohith/COURSE_WORK_JAN2010/GAME_THEORY_Y_NARAHARI/gametheory_assignments/ASSIGNMENT_1/eclipseprojects2/Assignment1_PureStrategyNE/log/executionLog.txt"); // opens the file
	std::string outputFileLocation = rootFolder + "/log/" + "executionLog.txt";
	cout << "outputFileLocation:" << outputFileLocation << endl;
	//outputFile.open("/home_fedora/GameTheory_Assignment_PSNE/Assignment1_PureStrategyNE/log/executionLog.txt"); // opens the file
	outputFile.open(outputFileLocation.c_str()); // opens the file
	cout << "here" << endl;
	if(!outputFile) { // file couldn't be opened
		cerr << "Error: file could not be opened" << endl;
		exit(1);
	}

	std::string finalResultsFileLocation = rootFolder + "/log/" + "finalResultsLog.txt";
	//finalResultsFile.open("/home/rohithdv/rohith/COURSE_WORK_JAN2010/GAME_THEORY_Y_NARAHARI/gametheory_assignments/ASSIGNMENT_1/eclipseprojects2/Assignment1_PureStrategyNE/log/finalResultsLog.txt"); // opens the file
	cout << "finalResultsFileLocation: " << finalResultsFileLocation <<  endl;
	//finalResultsFile.open("/home_fedora/GameTheory_Assignment_PSNE/Assignment1_PureStrategyNE/log/finalResultsLog.txt"); // opens the file
	finalResultsFile.open(finalResultsFileLocation.c_str());
	cout << "here" << endl;
	if(!finalResultsFile) { // file couldn't be opened
		cerr << "Error: file could not be opened" << endl;
		exit(1);
	}
}

int SFGame::readGameFromFile(std::string rootFolder, std::string inputFileName){
	string line, str3;
	ifstream myfile;
	//regex expression123("\\s+");
	boost::xpressive::sregex expression = boost::xpressive::sregex::compile( "\\s+" );  

	vector< string > result;

	//myfile.open("/home/rohithdv/rohith/COURSE_WORK_JAN2010/GAME_THEORY_Y_NARAHARI/gametheory_assignments/ASSIGNMENT_1/eclipseprojects2/Assignment1_PureStrategyNE/input/zero-sum-game_GAMBIT_FORMAT"); // opens the file
	cout << "here" << endl;
	std::string inputFileLocation = rootFolder + "/input/" + inputFileName;
	//myfile.open("/home_fedora/GameTheory_Assignment_PSNE/Assignment1_PureStrategyNE/input/zero-sum-game_GAMBIT_FORMAT"); // opens the file
	myfile.open(inputFileLocation.c_str());
	cout << "here" << endl;

	if(!myfile) { // file couldn't be opened
		cerr << "Error: file could not be opened" << endl;
		exit(1);
	}

	outputFile.precision(17);

	if (myfile.is_open())
	{
		int nooflinesEncountered = 0;
		int blankLineEncountered  = 0;
		while (! myfile.eof() )
		{
	cout << "here" << endl;
			getline (myfile,line);

			//cmatch what;
			//regex expression1("(Players:).*");
			//regex expression2("(Actions:).*");
			//regex expression3("(actions:).*");
			//regex expression4("[\r]+"); //blank line

			boost::xpressive::smatch what;
			boost::xpressive::sregex expression1 = boost::xpressive::sregex::compile( "(Players:).*" );
			boost::xpressive::sregex expression2 = boost::xpressive::sregex::compile( "(Actions:).*" );
			boost::xpressive::sregex expression3 = boost::xpressive::sregex::compile( "(actions:).*" );
			boost::xpressive::sregex expression4 = boost::xpressive::sregex::compile( "[\r]+" );//blank line

			if (line.empty())
			{
				// cout << "Blank line" << endl;
				blankLineEncountered = 1; // after this line the values in the file represent the utility values of the players
			}
			else if(boost::xpressive::regex_match(line, what, expression1))
			{
	cout << "here" << endl;
				// Players:
				cout <<	line << endl;
				cout << what[0] << endl;
				cout << what[1] << endl;
				cout << *(line.begin()) << endl;
				cout << *(line.end()) << endl;
	cout << "here******" << endl;
				
				nooflinesEncountered++;
				boost::xpressive::sregex_token_iterator i(line.begin(), line.end(), expression, -1);
				boost::xpressive::sregex_token_iterator j;


				string arr[2];
				unsigned count = 0;
				while(i != j)
				{
					arr[count] = *i;
					//cout << *i++ << endl;
					*i++;
					count++;
				}
				
				try
				{
	cout << "here" << endl;
					noofplayers = boost::lexical_cast<int>(arr[1]);
				}
				catch (const std::exception&)
				{
					noofplayers = 0;
				}
				if (noofplayers <= 0) {
					outputFile << "Invalid Number of Players Entry" << endl << endl;
					myfile.close();
					return -1;
				}

			}
			else if (boost::xpressive::regex_match(line, what, expression2))
			{
	cout << "here2" << endl;
				// Actions:
				//regex expression("\\s+");
				nooflinesEncountered++;
				boost::xpressive::sregex_token_iterator i(line.begin(), line.end(), expression, -1);
				boost::xpressive::sregex_token_iterator j;
				noofactions = new int[noofplayers];
				i++;
				int count = 0;
				while(i != j)
				{
					try
					{
						noofactions[count++] = boost::lexical_cast<int>(*i);
						*i++;
					}
					catch (const std::exception&)
					{
						noofplayers = 0;
					}
					if (noofplayers == 0 || noofactions[count-1] <= 0) {
						outputFile << "Invalid DATA - number of strategies" << endl << endl;
						myfile.close();
						return -1;
					}
				}
			}
			else if (boost::xpressive::regex_match(line, what, expression3))
			{
	cout << "here3" << endl;
				// actions::
				regex expression("\\s+");
				//nooflinesEncountered++;
			}
			else if (nooflinesEncountered == 2 && blankLineEncountered == 1) // and it is not a blank line
			{
	cout << "here5" << endl;
				// 3 lines are mandatory in the gambit file - 'Players' line  , 'Actions' line  and 'actions' (lowercase) line
				//regex expression("\\s+");
				//nooflinesEncountered++;
				boost::xpressive::sregex_token_iterator i(line.begin(), line.end(), expression, -1);
				boost::xpressive::sregex_token_iterator j;
				numberofStrategyProfiles = 1;
				for (int i=0; i< noofplayers; i++) {
					numberofStrategyProfiles *= noofactions[i];
				}

				utilityMatrix = new double[numberofStrategyProfiles*noofplayers];

				unsigned count = 0;
				while(i != j)
				{
					try
					{
						utilityMatrix[count] = boost::lexical_cast<double>(*i);
					}
					catch (const std::exception&)
					{
						utilityMatrix[count] = 0;
					}
					*i++;
					count++;
				}
			}
			else {
				 cout << "No donuts:" <<  "Line encoutered" << line << endl;
			}
		}
		if (nooflinesEncountered < 2 || blankLineEncountered == 0) {
			outputFile << "Invalid GAMBIT FILE " << endl << endl;
			myfile.close();
			return -1;
		}
		myfile.close();
	}
	outputFile << "DATA READ FROM INPUT FILE :  START " << endl;
	outputFile << "No of Players: " << noofplayers << endl;
	for (int h=0;h<noofplayers;h++ ){
		outputFile << "No of actions of player " << h << " is " << noofactions[h] << endl;
	}
	outputFile << "DATA READ FROM INPUT FILE :  END " << endl;
	initializeDataStructures();

	outputFile << endl << "PRINTING THE DATA STRUCTURES STORED IN MEMORY : START " << endl;
	for (int i=0; i < noofplayers; i++) {
		playerStrategyCircularLists[i]->display();
	}

	for (MyMap::const_iterator it = payoffMap.begin(); it != payoffMap.end(); ++it) {
		outputFile << "[ " << it->first << "] : { " ;
		for (int j=0; j< noofplayers; j++) {
			outputFile << it->second[j] << "  ";
		}
		outputFile << "}" << endl;
	}

	outputFile << "PRINTING THE DATA STRUCTURES STORED IN MEMORY : END" << endl << endl;

	outputFile << "PRINTING THE RESULTS OF ANALYSIS OF GAME : START " << endl << endl;
	// solveForDominantStrategies();

	return 1;
}


void SFGame::solveForDominantStrategies(){
	checkForDominantStrategies();
}

SFGame::~SFGame() {
	for (int i=0; i < noofplayers; i++) {
		delete playerStrategyCircularLists[i];
		playerStrategyCircularLists[i] = NULL;
	}
	delete[] playerStrategyCircularLists;

	delete[] utilityMatrix;

	// Allocate Memory for Strategy Structures

	for (int i=0;i<noofplayers; i++) {
		delete weaklyDOMINATEDStrategies_Type1[i];
		delete strictlyDOMINATEDStrategies[i];
		delete weaklyDOMINATEDStrategies_Type2[i];

		delete strictlyDOMINANTStrategies[i];
		delete weaklyDOMINANTStrategies_Type1[i];
		delete weaklyDOMINANTStrategies_Type2[i];

		delete eliminatedStrategies[i];

		for (int d=0;d<noofactions[i]; d++) {
			delete[] strictlyDOMINATEDCount[i][d];
			delete[] weaklyDOMINATEDCount[i][d];
			delete[] weaklyDOMINANTCount[i][d];
			delete[] strictlyDOMINANTCount[i][d];
		}
		delete[] strictlyDOMINATEDCount[i];
		delete[] weaklyDOMINATEDCount[i];
		delete[] weaklyDOMINANTCount[i];
		delete[] strictlyDOMINANTCount[i];
	}

	delete[] weaklyDOMINATEDStrategies_Type1;
	delete[] strictlyDOMINATEDStrategies;
	delete[] weaklyDOMINATEDStrategies_Type2;
	delete[] eliminatedStrategies;

	delete[] strictlyDOMINANTStrategies; // player x strategy
	delete[] weaklyDOMINANTStrategies_Type1; // player x strategy
	delete[] weaklyDOMINANTStrategies_Type2; // player x strategy

	outputFile.close();
	finalResultsFile.close();
}

int SFGame::initializeDataStructures(){

	playerStrategyCircularLists = new circularlist* [noofplayers];

	for (int j=0; j< noofplayers; j++) {
		// construct one circular list for each player corresponding to the no of strategies he has
		int noofstrategies = noofactions[j];
		playerStrategyCircularLists[j] = new circularlist();
		playerStrategyCircularLists[j]->updateList(j, noofstrategies);
	}


	int *stratProfile = new int[noofplayers];
	int counter = 0;

	for (int i = 0; i<numberofStrategyProfiles; i++) {
		generateNextStrategyProfile(&stratProfile);

		std::string stringFormat = "";
		double *utilProfile = new double[noofplayers];
		for (int j=0; j<noofplayers; j++) {
			utilProfile[j] = utilityMatrix[counter++];
			// cout << "stratProfile[j] " << stratProfile[j];
			std::string appendString = boost::lexical_cast<std::string>(stratProfile[j]);
			stringFormat.append(appendString.c_str());
			stringFormat.append(1, DELIMITER);
		}

		payoffMap.insert(std::make_pair(stringFormat, utilProfile));
	}
	delete[] stratProfile;

	// Allocate Memory for Strategy Structures
	weaklyDOMINATEDStrategies_Type1 = new bool* [noofplayers];
	strictlyDOMINATEDStrategies = new bool* [noofplayers];
	weaklyDOMINATEDStrategies_Type2 = new bool* [noofplayers];
	eliminatedStrategies = new bool* [noofplayers];

	strictlyDOMINANTStrategies = new bool* [noofplayers]; // player x strategy
	weaklyDOMINANTStrategies_Type1 = new bool* [noofplayers]; // player x strategy
	weaklyDOMINANTStrategies_Type2 = new bool* [noofplayers]; // player x strategy

	notDOMINANT = new bool* [noofplayers];

	strictlyDOMINATEDCount = new int** [noofplayers];
	weaklyDOMINATEDCount = new int** [noofplayers];
	weaklyDOMINANTCount = new int** [noofplayers];
	strictlyDOMINANTCount= new int** [noofplayers];
	undecided = new bool** [noofplayers];

	for (int i=0;i<noofplayers; i++) {
		weaklyDOMINATEDStrategies_Type1[i] = new bool[noofactions[i]];
		strictlyDOMINATEDStrategies[i] = new bool[noofactions[i]];
		weaklyDOMINATEDStrategies_Type2[i] = new bool[noofactions[i]];

		strictlyDOMINANTStrategies[i] = new bool[noofactions[i]];
		weaklyDOMINANTStrategies_Type1[i] = new bool[noofactions[i]];
		weaklyDOMINANTStrategies_Type2[i] = new bool[noofactions[i]];

		eliminatedStrategies[i] = new bool[noofactions[i]];

		strictlyDOMINATEDCount[i] = new int* [noofactions[i]];
		weaklyDOMINATEDCount[i] = new int* [noofactions[i]];
		weaklyDOMINANTCount[i] = new int* [noofactions[i]];
		strictlyDOMINANTCount[i] = new int* [noofactions[i]];
		undecided[i] = new bool* [noofactions[i]];

		notDOMINANT[i] = new bool[noofactions[i]];

		for (int p=0; p< noofactions[i]; p++) {
			strictlyDOMINATEDCount[i][p] = new int [noofactions[i]];
			weaklyDOMINATEDCount[i][p] = new int [noofactions[i]];
			weaklyDOMINANTCount[i][p] = new int [noofactions[i]];
			strictlyDOMINANTCount[i][p] = new int [noofactions[i]];
			undecided[i][p] = new bool [noofactions[i]];
		}
	}

	resetStrategyDataStructures();
	resetEliminatedStrategies();
	return 1;
}

void SFGame::generateNextStrategyProfile_ExceptPlayer_i(int **stratProfile, int excludedPlayer) {
	// ensure stratprofile is of size = sizeofArray
	bool rollback = false;

	// advance pointers
	for (int j=0; j< noofplayers; j++) {
		if (j == excludedPlayer) continue;
		rollback = playerStrategyCircularLists[j]->incrementPointer();
		if (!rollback) {
			break;
		}
	}

	// get values from each of the player lists
	for (int j=0; j< noofplayers; j++) {
		if (j == excludedPlayer) continue;
		(*stratProfile)[j] = playerStrategyCircularLists[j]->returnCurrPointerValue();
	}
}

void SFGame::generateNextStrategyProfile(int **stratProfile) {

	bool rollback = false;

	// advance pointers
	for (int j=0; j< noofplayers; j++) {
		rollback = playerStrategyCircularLists[j]->incrementPointer();
		if (!rollback) {
			break;
		}
	}

	// get values from each of the player lists
	for (int j=0; j< noofplayers; j++) {
		(*stratProfile)[j] = playerStrategyCircularLists[j]->returnCurrPointerValue();
	}
}

// evaluates any strictly dominant strategies, weakly dominant strategies
// strictly dominated strategies, weakly dominated strategies.
void SFGame::checkForDominantStrategies(){
	int *stratProfile = new int[noofplayers];
	//bool notDOMINANT = false;
	bool weaklyDOMINANTType2 = false;
	bool weaklyDOMINANTType1 = false;
	int noofrounds = 1;


	for (int i=0; i< noofplayers; i++){
		//select player i
		// find out no of strategy tuples involving action k of player i
		// this is needed to determine the strictly dominated strategies.
		// strictly dominated strategies will be dominated "noofrounds" times by some other strategy
		// basically noofrounds is an count on the no of possible values of s_{-i}
		noofrounds = 1;
		for (int l=0; l < noofplayers; l++) {
			if (l == i) continue;
			int count = noofactions[l];
			for (int w=0; w < noofactions[l]; w++) {
				if (eliminatedStrategies[l][w]) {
					count--;// remove the eliminated strategies of the player
				}
			}
			if (count) { // non-zero value of count
				noofrounds *= count;
			}
			else {
				cout << " THIS SHOULD NOT HAPPEN IDEALLY ! Player " << i << "'s strategy set is 0! CHECK THIS ! " << endl;
				noofrounds *= 1;
			}
		}

		// choose an action of player i
		for (int k=0; k < noofactions[i]; k++) {
			// we will now calculate the relation of action k with respect to other strategies of player i
			// for all possible values of s_{-i}

			// might have been eliminated due to it being a dominated strategy
			if (eliminatedStrategies[i][k] == true) {
				continue;
			}

			notDOMINANT[i][k] = false;
			weaklyDOMINANTType1 = false;
			weaklyDOMINANTType2 = false;

			for (int l=0; l < noofplayers; l++) {
				playerStrategyCircularLists[l]->reset(); // resets the header to point to last element of the list
			}

			for (int j=0; j< noofrounds; j++) {
				// Fix a particular s_{-i} value
				generateNextStrategyProfile_ExceptPlayer_i(&stratProfile, i);

				// evaluate what is the relation between k and other strategies of player i
				// with respect to the above s_{-i} value in terms of the utility provided
				stratProfile[i] = k+1;

				double w = getUtilityValue(stratProfile, i);

				// for a fixed s_{-i}, compare strategy k of player i with other of its strategies
				for (int g = 0; g< noofactions[i]; g++) {
					// for each of player i's strategy, check if it is dominant strategy
					// fix other player's strategy
					if (g== k) continue;
					if (eliminatedStrategies[i][g] == true) {
						continue;
					}
					stratProfile[i] =g+1;
					double v = getUtilityValue(stratProfile, i);
					if (w < v){
						if (!notDOMINANT[i][k]) {
							outputFile << "Strategy " << k << " of player " << i << " is not (weakly/strongly) dominant " << endl;
							notDOMINANT[i][k] = true;
							weaklyDOMINANTType2 = false;
							weaklyDOMINANTType1 = false;
						}
						strictlyDOMINATEDCount[i][k][g] += 1;
						// break;
					}
					else if (w == v) {
						weaklyDOMINANTType2 = true;
						weaklyDOMINATEDCount[i][k][g] += 1;
						weaklyDOMINANTCount[i][k][g] += 1;
					}
					else {
						strictlyDOMINANTCount[i][k][g] += 1;
						weaklyDOMINANTType1 = true;
					}
				}
				/*if (notDOMINANT) {
					break;
				}*/
			}

			if (!notDOMINANT[i][k]) {
				if (weaklyDOMINANTType1 && weaklyDOMINANTType2) {
					outputFile << "Strategy " << k << " of player " << i << " is WEAKLY DOMINANT (TYPE 1) " << endl;
					weaklyDOMINANTStrategies_Type1[i][k] = true;

					for (int y=0; y < noofactions[i]; y++) {
						if (y == k) continue;
						weaklyDOMINANTStrategies_Type1[i][y] = false;
						weaklyDOMINATEDStrategies_Type1[i][y] = true;
					}
					//break; // no need to search for any other dominant strategy as it is unique !
				}
				else if (weaklyDOMINANTType2) {
					outputFile << "Strategy " << k << " of player " << i << " is WEAKLY DOMINANT (TYPE 2) " << endl;
					weaklyDOMINANTStrategies_Type2[i][k] = true;
					// can have multiple type 2 dominant strategy
				}
				else {
					outputFile << "Strategy " << k << " of player " << i << " is STRICTLY DOMINANT " << endl;
					strictlyDOMINANTStrategies[i][k] = true; // strategies in circular list are stored from 1, 2, .... and not 0, 1, ...

					for (int y=0; y < noofactions[i]; y++) {
						if (y == k) continue;
						strictlyDOMINANTStrategies[i][y] = false;
						strictlyDOMINATEDStrategies[i][y] = true;
					}
					//break; // no need to search for any other dominant strategy as it is unique !
				}
			}
			else {
				// k is not a dominant strategy. it is either dominated or not. in the later case we decide anything about k
				// Check if k is a dominated (strictly /weakly) strategy

				for (int h=0;h < noofactions[i]; h++) {
					if (strictlyDOMINATEDCount[i][k][h] == noofrounds) {
						// definitely h dominates over k.and hence k is dominated strategy
						strictlyDOMINATEDStrategies[i][k] = true;
						outputFile << "Strategy " << k << " of player " << i << " is STRICTLY DOMINATED by Strategy " << h << endl;
						break;
					}
					else if ((weaklyDOMINATEDCount[i][k][h]) == noofrounds) {
						weaklyDOMINATEDStrategies_Type2[i][k] = true;
						outputFile << "Strategy " << k << " of player " << i << " is WEAKLY DOMINATED (TYPE 2) by Strategy " << h << endl;
					}
					else if ((strictlyDOMINATEDCount[i][k][h] + weaklyDOMINATEDCount[i][k][h]) == noofrounds ) {
						weaklyDOMINATEDStrategies_Type1[i][k] = true;
						outputFile << "Strategy " << k << " of player " << i << " is WEAKLY DOMINATED (TYPE 1) by Strategy " << h << endl;
					}
					else {
						if (k == h) continue;
						undecided[i][k][h] = true;
						outputFile << "Relationship between strategy " << k << " and strategy " << h << " of player " << i << " is neither DOMINATED nor DOMINANT " << endl;
					}
				}
			}
		}
	}
	delete[] stratProfile;
}

double SFGame::getUtilityValue(int *stratProfile, int player) {

	for (int r=1; r < noofplayers; r++) {
		if (stratProfile[r] == 0) { // stratprofile stores actions starting from 1,2, ...etc
			outputFile << "MAJOR ERROR !! THIS SHOULD NOT HAPPEN!! " << endl;
			exit(0);
		}
	}

	string findString = "";
	for (int i=0; i< noofplayers; i++) {
		std::string appendString = boost::lexical_cast<std::string>(stratProfile[i]);
		findString.append(appendString.c_str());
		findString.append(1, DELIMITER);
	}
	double *arr = payoffMap.find(findString)->second;
	double val = arr[player];
	return val;
}

void SFGame::iteratedEliminationOfDominatedStrategies() {
	// eliminate strictly dominated strategies for each player in one round
	bool dominatedStrategyIsPresent = true;
	int dominatedStrategyForPlayer_j = -1;

	resetEliminatedStrategies();

	int itCount = 0;
	while (dominatedStrategyIsPresent) {
		itCount++;
		outputFile << endl << "ITERATION " << itCount << " START"<< endl << endl;
		resetStrategyDataStructures();
		dominatedStrategyIsPresent = false;

		checkForDominantStrategies();

		logIterativeEliminationResults(outputFile, itCount);
		logIterativeEliminationResults(finalResultsFile, itCount);

		for (int i=0; i<noofplayers; i++) {
			for (int k=0; k < noofactions[i]; k++) {
				if (!eliminatedStrategies[i][k] && strictlyDOMINATEDStrategies[i][k]) {
					dominatedStrategyForPlayer_j = k;
					// at least one dominated strategy is present
					dominatedStrategyIsPresent = true;

					// this will remove the strategy from the circular list
					playerStrategyCircularLists[i]->deleteEntry(dominatedStrategyForPlayer_j+1);
					// adding here would eliminate the possibility that the strategy is used again in checking for dominant strategies
					eliminatedStrategies[i][dominatedStrategyForPlayer_j] = true;
					outputFile << endl << "Eliminating Strategy " << dominatedStrategyForPlayer_j << " for player " << i << " as it is STRICTLY DOMINATED" << endl;
					break;
				}
				else if (!eliminatedStrategies[i][k] && weaklyDOMINATEDStrategies_Type1[i][k]) {
					dominatedStrategyForPlayer_j = k;
					// at least one dominated strategy is present
					dominatedStrategyIsPresent = true;

					// this will remove the strategy from the circular list
					playerStrategyCircularLists[i]->deleteEntry(dominatedStrategyForPlayer_j+1);
					// adding here would eliminate the possibility that the strategy is used again in checking for dominant strategies
					eliminatedStrategies[i][dominatedStrategyForPlayer_j] = true;
					outputFile << endl << "Eliminating Strategy " << dominatedStrategyForPlayer_j << " for player " << i << " as it is WEAKLY DOMINATED (TYPE 1)" << endl;
					break;
				}
			}
		}
		outputFile << endl << "ITERATION " << itCount << " END"  << endl;
	}

	itCount = -1;
	logIterativeEliminationResults(outputFile, itCount);
	logIterativeEliminationResults(finalResultsFile, itCount);

	resetplayerStrategyCircularLists();
	resetStrategyDataStructures();
	resetEliminatedStrategies();
}


void SFGame::resetplayerStrategyCircularLists() {

	// construct one circular list for each player corresponding to the no of strategies he has
	for (int j=0; j< noofplayers; j++) {

		// delete previously built circular list
		if (playerStrategyCircularLists[j] != NULL) {
			delete playerStrategyCircularLists[j];
			playerStrategyCircularLists[j] = NULL;
		}
		playerStrategyCircularLists[j] = new circularlist();
		playerStrategyCircularLists[j]->updateList(j, noofactions[j]);
	}
}

void SFGame::resetStrategyDataStructures() {

	for (int j=0; j<noofplayers; j++) {
		for (int k=0; k < noofactions[j]; k++) {
			strictlyDOMINATEDStrategies[j][k] = false;
			strictlyDOMINANTStrategies[j][k] = false;
			weaklyDOMINATEDStrategies_Type1[j][k] = false;
			weaklyDOMINATEDStrategies_Type2[j][k] = false;
			weaklyDOMINANTStrategies_Type1[j][k] = false;
			weaklyDOMINANTStrategies_Type2[j][k] = false;
			// eliminatedStrategies[j][k] = false;
			notDOMINANT[j][k] = false;


			for (int g=0; g < noofactions[j]; g++) {
				weaklyDOMINANTCount[j][k][g] = 0; // player x strategy x strategy
				strictlyDOMINANTCount[j][k][g] = 0; // player x strategy x strategy
				strictlyDOMINATEDCount[j][k][g] = 0; // player x strategy x strategy
				weaklyDOMINATEDCount[j][k][g] = 0; // player x strategy x strategy
				undecided[j][k][g] = false; // player x strategy x strategy
			}
		}
	}
}

void SFGame::resetEliminatedStrategies() {
	for (int j=0; j<noofplayers; j++) {
		for (int k=0; k < noofactions[j]; k++) {
			eliminatedStrategies[j][k] = false;
		}
	}
}


void SFGame::findNashEquilibriaByTabuSearch() {
	// Algorithm:
	//Initialize T to be empty
	//Choose the starting solution x_i
	//until the termination criteria is satisfied {
	//	i = next player
	//	x = best response action of the player
	//	remove the oldest item in T is |T| = L
	//	push x onto T
	//
	int **bestResponseList = new int* [noofplayers];

	sampleCount = new int[noofplayers];

	for (int k=0; k< noofplayers; k++) {
		bestResponseList[k] = new int[noofactions[k]];
		sampleCount[k] = 1;
	}

	//int NO_OF_ROUNDS = 10;
	int *stratProfile = new int[noofplayers];
	bool stratProfileChangedFlag = false;

	//stratProfile contains strategies of players that start with 1, 2, ....!! NOTE !!

	bool allPathsExhaustedForSomePlayer = false;

	outputFile << "STARTING BEST RESPONSE DYNAMICS USING TABU SEARCH METHOD " <<  endl;
	finalResultsFile << "STARTING BEST RESPONSE DYNAMICS USING TABU SEARCH METHOD " <<  endl;

	for (int i=0; i < NO_OF_ROUNDS; i++) {
		getRandomStrategyProfile(stratProfile);
		stratProfileChangedFlag = true;
		allPathsExhaustedForSomePlayer = false;

		string profile="";
		for (int j=0; j <noofplayers; j++) {
			std::string appendString = boost::lexical_cast<std::string>(stratProfile[j]);
			profile.append(appendString.c_str());
			profile.append(1, DELIMITER);
		}
		outputFile << endl << endl;
		outputFile << "STARTING ROUND " << i << endl;
		outputFile << "SEED PROFILE IS " << profile << endl;

		while (stratProfileChangedFlag) {
			stratProfileChangedFlag = false;
			for (int j1=0; j1 < noofplayers; j1++) {
				bool res = isStratProfileBestResponseForPlayer_i(stratProfile, j1);
				if (!res) {
					getBestResponseListInDecreasingOrder(bestResponseList[j1], stratProfile, j1 );
					int count = 0;
					while (true) {
						int currStrategy = stratProfile[j1];
						// not +1 is due to the strategy naming convention. We name strategies from 0,1,2....everywhere
						// except when we are looking up in the hash map
						if (count > (noofactions[j1]-1)) {
							// all the strategies are there in the tabu list. Cannot proceed with the
							// best response dynamics. Discard this entry and start with the next round
							allPathsExhaustedForSomePlayer = true;
							break;
						}
						int newStrategy = (bestResponseList[j1][count++] + 1);

						// there is a decision to be made here. we can either do this or not ! we are avoiding repeating the same strategy
						// however it is interesting to see what happens if we allow repeating the same strategy.Check this out later
						// by commenting the line below!
						if (newStrategy == currStrategy) continue;

						stratProfile[j1] = newStrategy;

						string profile="";
						for (int j=0; j <noofplayers; j++) {
							std::string appendString = boost::lexical_cast<std::string>(stratProfile[j]);
							profile.append(appendString.c_str());
							profile.append(1, DELIMITER);
						}

						if (IsStratProfileInTabuList(stratProfile)) {
							outputFile << "Strategy " << (newStrategy-1) << " for player " << j1 << " is already in tabu list. " << "Current Strategy Profile : " << profile <<  endl;
							stratProfile[j1] = currStrategy;
							continue;
						}
						else {
							outputFile << "Changing Strategy " << (currStrategy-1) << " to Strategy " << (newStrategy-1) << " for player " << j1 << "Current Strategy Profile : " << profile << endl;
							stratProfileChangedFlag = true;
							updateTabuArray(stratProfile); // by default this will flush out old entries based on TABU_TENURE
							break;
						}
					}
				}
				if (allPathsExhaustedForSomePlayer ==  true) {
					break;
				}
			} // end for
			if (allPathsExhaustedForSomePlayer ==  true) {
				break;
			}
		}// end while

		if (!allPathsExhaustedForSomePlayer) {
			logPSNEResults(outputFile, stratProfile);

			string findString = "";
			for (int i1=0; i1< noofplayers; i1++) {
				std::string appendString = boost::lexical_cast<std::string>(stratProfile[i1]);
				findString.append(appendString.c_str());
				findString.append(1, DELIMITER);
			}
			if (NEMap.count(findString) == 0) {
				NEMap.insert(std::make_pair(findString, &PSNE));
				finalResultsFile << "In Iteration " << i << ",  ";
				logPSNEResults(finalResultsFile, stratProfile);
				finalResultsFile << "The above PSNE was ONLY found by TABU SEARCH METHOD!!" << endl;
			}
			else { // can log just to show that NE was achieved through tabu search method !
				finalResultsFile << "In Iteration " << i << ",  ";
				logPSNEResults(finalResultsFile, stratProfile);
				finalResultsFile << "The above PSNE was ALSO found by earlier methods!!" << endl;
			}
		}
		else {
			outputFile << "NO PSNE could be found in Iteration " << i << " Of TABU SEARCH ALGORITHM !"<< endl;
			finalResultsFile << "NO PSNE could be found in Iteration " << i << " Of TABU SEARCH ALGORITHM !" <<  endl;
		}
		resetTabuArray();
		outputFile << "ENDING ROUND " << i << endl;
	} // end for

	outputFile << "ENDING BEST RESPONSE DYNAMICS USING TABU SEARCH METHOD " <<  endl;
	finalResultsFile << "ENDING BEST RESPONSE DYNAMICS USING TABU SEARCH METHOD " <<  endl;

	delete[] stratProfile;
	delete[] sampleCount;

	for (int k=0; k< noofplayers; k++) {
		delete bestResponseList[k];
	}
	delete[] bestResponseList;
}

void SFGame::logPSNEResults(ofstream& out, int *stratProfile) {
	out  << "PURE STRATEGY NASH EQUILIBRIUM FOUND ! It is given below " << endl;
	for (int k=0; k< noofplayers; k++) {
		out << "Player " << k << ": Strategy: " << (stratProfile[k]-1) << endl;
	}
}

void SFGame::getRandomStrategyProfile(int *stratProfile) {

	int randStrategy = 0;

	for (int i=0; i < noofplayers; i++) {
		randStrategy = getRandomNumberUsingBoostLibrary(1, noofactions[i], sampleCount[i]++, i);
		stratProfile[i] = randStrategy;
	}
}

int SFGame::getRandomNumberUsingBoostLibrary(int min, int max, int sampleCount, int player) {
	// std::cout << deg() << " " << deg() << " " << deg() << std::endl;

	base_generator_type generator(42u);
	// seeding with current time !
	generator.seed(static_cast<unsigned int>(std::time(0)));

	// as a degenerate case, you can set min = max for uniform_int
	boost::uniform_int<> uni_dist(min, max);
	boost::variate_generator<base_generator_type&, boost::uniform_int<> > deg(generator, uni_dist);

	int value;
	// randomize based on the samplecount and player ids
	// this is just to ensure different random numbers are generated when different
	// players are used
	for (int i=0; i< (sampleCount*(player+1)); i++) {
		value = deg();
	}
	return value;
}

bool SFGame::isStratProfileBestResponseForPlayer_i(int *stratProfile, int player){

	double w = getUtilityValue(stratProfile, player);
	int currentStrategy = stratProfile[player];

	for (int i=0; i< noofactions[player]; i++) {
		//if ((i+1) == stratProfile[player]) {
		// bug fix - rohith - 2nd MArch 2010
		if ((i+1) == currentStrategy) {
			continue; // i+1 is done as strategies start from 1 in stratprofile
		}
		stratProfile[player] = i+1;
		double v = getUtilityValue(stratProfile, player);
		if (v > w) {
			// note that this is strict inequality. we dont consider case if same utility is got by different strategy
			stratProfile[player] = currentStrategy;
			return false;
		}
	}
	stratProfile[player] = currentStrategy;
	return true;
}

int SFGame::getNextBestResponse(int *bestResponseList, int index1) {
	return 1;
}

void SFGame::updateTabuArray(int *stratProfile) {

	string profile = "";
	for (int i=0; i <noofplayers; i++) {
		std::string appendString = boost::lexical_cast<std::string>(stratProfile[i]);
		profile.append(appendString.c_str());
		profile.append(1, DELIMITER);
	}
	tabuCounter = (tabuCounter)%TABU_TENURE;
	tabuList[tabuCounter++] = profile;

	//	outputFile << "PRINTING TABU CONTENTS START " << endl;
	//	for (int i=0; i < TABU_TENURE; i++) {
	//		outputFile << tabuList[i] << ";";
	//	}
	//	outputFile << endl << "PRINTING TABU CONTENTS END " << endl;
}

void SFGame::resetTabuArray() {
	for (int i=0; i<TABU_TENURE; i++) {
		tabuList.at(i) = "";
	}
	tabuCounter = 0;
}

void SFGame::getBestResponseListInDecreasingOrder(int *bestResponseList, int *stratProfile, int player ){

	// This function basically ranks the strategies of player and returns in the decresing order of utilities
	// provided by these strategies, keeping the other strategies of other players as fixed.

	int numberOfStrategies = noofactions[player];
	int *bestResponseValuesList = new int[numberOfStrategies];
	int currentStrategy = stratProfile[player];
	int *rankList = new int[numberOfStrategies];

	// collect the best reponse values for all strategies of player
	for (int i=0; i< numberOfStrategies; i++) {
		stratProfile[player] = i+1;
		bestResponseValuesList[i] = getUtilityValue(stratProfile, player);
	}

	// reset to original value
	stratProfile[player] = currentStrategy;

	// rank the best response values by noting down for how many strategies a particular strategy gives a better/equal utility
	// this will the rank of that strategy
	for (int h=0; h<numberOfStrategies; h++) {
		int currValue = bestResponseValuesList[h];
		rankList[h] = 0;
		for (int j=0; j<numberOfStrategies; j++) {
			if (j == h) continue;
			if (currValue >= bestResponseValuesList[j]) {
				rankList[h]++;
			}
		}
	}

	// the max value of rank of a strategy can be atmost equal to numberOfStrategies-1)
	// now based on the rank of the strategies, up date the bestresponse list by iteratively considering
	// rank values = (numberOfStrategies -1), (numberOfStrategies-2), ... 1, 0
	int currMaxCount = numberOfStrategies-1;

	bool *alreadyConsidered = new bool[numberOfStrategies];
	for (int y=0; y<numberOfStrategies; y++) {
		alreadyConsidered[y] = false;
	}

	int count = 0;
	bool entryFound = false;

	while (count != numberOfStrategies) {
		entryFound = false;
		for (int p=0; p<numberOfStrategies; p++) {
			if (!alreadyConsidered[p] && rankList[p] == currMaxCount) {
				bestResponseList[count] = p;
				alreadyConsidered[p] = true;
				count = count + 1;
				entryFound = true;
				break;
			}
		}
		if(!entryFound) {
			currMaxCount -= 1; // no entries could be found with this value
			// decrease it to find the next possible max value
		}
	}

	delete[] alreadyConsidered;
	delete[] bestResponseValuesList;
	delete[] rankList;
}

bool SFGame::IsStratProfileInTabuList(int *stratProfile) {
	string profile = "";
	for (int i=0; i <noofplayers; i++) {
		std::string appendString = boost::lexical_cast<std::string>(stratProfile[i]);
		profile.append(appendString.c_str());
		profile.append(1, DELIMITER);
	}

	for (int j=0; j< TABU_TENURE; j++){
		if (!profile.compare(tabuList.at(j))) {
			return true;
		}
	}
	return false;
}

void SFGame::logIterativeEliminationResults(ofstream& out, int& itCount) {
	// LOGGING PURPOSES ONLY
	bool isGameDominantSolvable = true;
	string stringFormat = "";
	if (itCount == 1) {
		// Print Strictly Dominant  Strategies of the players
		out << endl << endl << "**** Statistics related to Strictly Dominant Strategies of the players **** START ****" << endl << endl;

		int *survivorStrategySet = new int[noofplayers];
		for (int j=0; j< noofplayers; j++) {
			int cnt = 0;
			for (int k=0; k< noofactions[j]; k++) {
				if (strictlyDOMINANTStrategies[j][k]) {
					if (cnt == 0) {
						out << "Strictly Dominant Strategy of Player " << j << " are  " << endl;
					}
					out << "Strategy " << k << endl << endl;
					cnt++;
					std::string appendString = boost::lexical_cast<std::string>(k+1);
					stringFormat.append(appendString.c_str());
					stringFormat.append(1, DELIMITER);
					survivorStrategySet[j] = k;
				}
			}
			if (!cnt) {
				isGameDominantSolvable = false;
				out << "There is no strictly dominant strategy for player " << j << endl;
			}
		}
		if (isGameDominantSolvable) {
			out << "PSNE for the game CAN be resolved through iterated elimination of dominant strategies ! " << endl;
			out << "SDSE (Strictly Dominant Strategy Equilibrium)  for the game is given below " << endl;
			for (int f=0; f<noofplayers; f++) {
				out << "Player " << f  << ": Strategy : " << survivorStrategySet[f] << endl;
			}
			NEMap.insert(std::make_pair(stringFormat, &SDSE));
		}
		else {
			out << "There is no SDSE (Strictly Dominant Strategy Equilibrium)  for the game " << endl;
		}
		out << endl << "**** Statistics related to Strictly Dominant Strategies of the players **** END ****" << endl;

		for (int f=0; f<noofplayers; f++) {
			// reset
			survivorStrategySet[f] = -1;
		}
		isGameDominantSolvable = true;
		// Print Weakly Dominant  Strategies of the players
		out << endl << endl << "**** Statistics related to Weakly Dominant Strategies (Type 1) of the players **** START ****" << endl << endl;

		for (int j=0; j< noofplayers; j++) {
			int cnt = 0;
			for (int k=0; k< noofactions[j]; k++) {
				if (weaklyDOMINANTStrategies_Type1[j][k]) {
					if (cnt == 0) {
						out << "Weakly Dominant Strategy (Type 1) of Player " << j << " are  " << endl;
					}
					out << "Strategy " << k << endl << endl;
					cnt++;
					std::string appendString = boost::lexical_cast<std::string>(k+1);
					stringFormat.append(appendString.c_str());
					stringFormat.append(1, DELIMITER);
					survivorStrategySet[j] = k;
				}
			}
			if (!cnt) {
				isGameDominantSolvable = false;
				out << "There is no weakly dominant strategy (Type 1) for player " << j << endl;
			}
		}
		if (isGameDominantSolvable) {
			out << "PSNE for the game CAN be resolved through iterated elimination of dominant strategies ! " << endl;
			out << "WDSE (Weakly Dominant (Type 1) Strategy Equilibrium)  for the game is given below " << endl;
			for (int f=0; f<noofplayers; f++) {
				out << "Player " << f  << ": Strategy : " << survivorStrategySet[f] << endl;
			}
			NEMap.insert(std::make_pair(stringFormat, &WDSE));
		}
		else {
			out << "There is no WDSE (Weakly Dominant (Type 1) Strategy Equilibrium)  for the game " << endl;
		}
		out << endl << "**** Statistics related to Weakly Dominant (Type 1) Strategies of the players **** END ****" << endl;
	}
	else if (itCount == -1){
		// Print Undominated Strategies of the players
		out << endl << endl << "**** Statistics related to Undominated Strategies (AFTER ITERATIVE ELIMINATION OF DOMINANT STRATEGIES) of the players **** START ****" << endl << endl;

		int val = 0;
		int *survivorStrategySet = new int[noofplayers];
		for (int j=0; j< noofplayers; j++) {
			val = 0;
			out << "Undominated Strategies of Player " << j << " are  " << endl;
			for (int k=0; k< noofactions[j]; k++) {
				if (!eliminatedStrategies[j][k]) {
					out << "Strategy " << k << endl;
					val++;
					std::string appendString = boost::lexical_cast<std::string>(k+1);
					stringFormat.append(appendString.c_str());
					stringFormat.append(1, DELIMITER);
					survivorStrategySet[j] = k;
				}
			}
			if (val != 1) { // every player should have one unique strategy left out
				isGameDominantSolvable = false;
			}
		}

		if (isGameDominantSolvable) {
			out << "PSNE for the game CAN be resolved through iterated elimination of dominant strategies ! " << endl;
			out << "IDSE (Iteratively Dominant Strategy Equilibrium)  for the game is given below " << endl ;
			for (int f=0; f<noofplayers; f++) {
				out << "Player " << f  << ": Strategy : " << survivorStrategySet[f] << endl;
			}
			NEMap.insert(std::make_pair(stringFormat, &IDSE));
		}
		else {
			out << "PSNE for the game CANNOT be resolved through iterated elimination of dominant strategies ! " << endl;
		}

		out << endl << endl << "**** Statistics related to Undominated Strategies (AFTER ITERATIVE ELIMINATION OF DOMINANT STRATEGIES) of the players **** END ****" << endl << endl ;
	}
}

void SFGame::displayALLPSNE(){
	logALLPSNE(outputFile);
	logALLPSNE(finalResultsFile);

	outputFile << endl << "PRINTING THE RESULTS OF ANALYSIS OF GAME : END " << endl;
	//outputFile << endl << "PRINTING MEMORY-FREEING RELATED LOG " << endl ;
}

void SFGame::logALLPSNE(ofstream& out){

	out<< endl << "AGGREGATED LIST OF ALL PSNE FOUND BY THE PROGRAM USING DIFFERENT METHODS " << endl;
	//regex expression("[\\|]");
	boost::xpressive::sregex expression = boost::xpressive::sregex::compile("[\\|]");

	int strat = -1;
	int cnt = 0;
	int player = 0;
	BOOST_FOREACH(MyMap::value_type i, NEMap) {
		string NE = i.first;
		boost::xpressive::sregex_token_iterator i1(NE.begin(), NE.end(), expression, -1);
		boost::xpressive::sregex_token_iterator j;
		player = 0;
		out << "NE Number: " << ++cnt << " | NE Type: " ;
		if (i.second[0] == PSNE) {
			out << "PSNE" << endl;
		}
		else if (i.second[0] == SDSE){
			out << "SDSE" << endl;
		}
		else if (i.second[0] == WDSE){
			out << "WDSE" << endl;
		}
		else if (i.second[0] == IDSE){
			out << "IDSE" << endl;
		}

		while (i1!=j) {
			string h = *i1++;
			out << "Player " << player++  << ": Strategy: ";
			strat = atoi(h.c_str())-1 ;
			out << strat << endl;
		}
	}
	 out << "Total Number of PSNE: " << cnt << endl;
}
